package com.dyw.Day18;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Devil
 * @create 2022-01-27-23:36
 *
 * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 *
 * 思路: 题目要求使用层序遍历并且根据返回值  首先判断树为空的情况 后面则是使用队列辅助层序遍历二叉树
 * 为了将每层的数据封装成一个List集合 在原本的层序遍历基础上进行了改进 在while循环中加上了一个for循环进一步遍历队列(一整层)
 * 最后将每层的List集合 添加到最后要换回的List集合中
 */
@SuppressWarnings("all")
public class Demo01 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        //创建一个队列 用来存储一棵树每一层的左子树 右子树(依次)
        if(root==null){
            return new LinkedList<>();
        }
        Deque<TreeNode> deque = new LinkedList<>();
        List<List<Integer>> lists = new LinkedList<>();

        deque.add(root);
        while(!deque.isEmpty()){
            int count = deque.size();
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 0; i < count; i++) {
                TreeNode cur = deque.pop();
                list.add(cur.val);
                if(cur.left!=null){
                    deque.add(cur.left);
                }
                if(cur.right!=null){
                    deque.add(cur.right);
                }
            }
            lists.add(list);
        }
        return lists;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}